package com.zhupf.part7;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zhupf
 * @date 2024年12月03日 16:02
 * @Description
 */
public class LinkNodeCode {
    public static void main(String[] args) {
        ListNode node = new ListNode(1,null);
        ListNode node1 =  new ListNode(2,node);
        node.next = node1;
        System.out.println(hasLoopV3(node1));

    }

    ////////////////////////////////////////////////链表的中间结点 //////////////////////////

    public ListNode middleNode(ListNode head) {
        ListNode fast= head;
        ListNode slow= head;
        while (fast != null && fast.next != null ){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


    ///////////////////////////// 删除链表第N个节点///////////////////////////////////


    /**
     * 双指针   还有计算链表的长度，直接遍历一遍，然后再遍历到倒数第n个节点，还有就是栈，全部压栈，然后弹出第n个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode h = head;
        for (int i = 0; i < n; i++) {
            h = h.next;
        }
        ListNode node = dummy;
        while (h != null) {
            node = node.next;
            h = h.next;
        }
        node.next = node.next.next;
        return dummy.next;
    }




    /////////////////////////////////////////////// 合并两个有序链表////////////////////////

    /**
     * 迭代
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pre = new ListNode(0, null);
        ListNode cur = pre;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
        }
        cur.next = list1 != null ? list1 : list2;
        return pre.next;
    }


    /**
     * 递归
     *
     * @param list1
     * @param list2
     * @return
     */
    public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list1 == null || list2 == null) {
            return list1 == null ? list2 : list1;
        }
        ListNode newNode;
        if (list1.val <= list2.val) {
            newNode = mergeTwoLists2(list1.next, list2);
            list1.next = newNode;
            newNode = list1;
        } else {
            newNode = mergeTwoLists2(list1, list2.next);
            list2.next = newNode;
            newNode = list2;
        }
        return newNode;
    }

    ///////////////////////////////////////链表中环的检测/////////////////////////////////////////////////////

    /**
     * 环的切点
     *
     * @param head
     * @return
     */
    public static ListNode hasLoopV3(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode h = head;
                while (fast != h) {
                    fast = fast.next;
                    h = h.next;
                }
                return fast;
            }
        }
        return null;
    }

    /**
     * hash
     * @param head
     * @return
     */
    public static boolean hasLoopV1(ListNode head) {
            if(head == null || head.next == null){
                return false;
            }
            ListNode slow = head;
            ListNode fast = head;
            while (slow != null && fast != null && fast.next != null){
                slow = slow.next;
                fast = fast.next.next;
                if(slow== fast){
                    return true;
                }

            }
            return false;
    }

    /**
     * 快慢指针
     * @param head
     * @return
     */
    public static boolean hasLoopV2(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        Set<ListNode> set = new HashSet<>();
        while (head != null){
            if(set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }


///////////////////////////////////////链表反转/////////////////////////////////////////////////////
    /**
     * 链表反转
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode h = head;
        ListNode ans = null;
        ListNode next;
        while (h != null){
            next = h.next;
            h.next = ans;
            ans = h;
            h = next;
        }
        return ans;
    }

    public static ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode h = head;
        ListNode ans = new ListNode(0,null);
        ListNode next;
        while (h != null){
            next = h.next;
            h.next = ans.next;
            ans.next = h;
            h = next;
        }
        return ans.next;
    }

    /**
     * 递归
     * @param head
     * @return
     */
    public static ListNode reverseList3(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode ans = reverseList3(head.next);
        head.next.next = head;
        head.next = null;
        return ans;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
